// 基于双端链表实现一个可迭代的列表类，它拥有 push、add（push的别名方法）、append（push的别名方法）、pushLeft、addpenLeft（pushLeft的别名方法）、pop、clear、remove、drop、get、includs、contains（includs的同名方法）、filter、map方法、length属性。给出代码注释。

import { isNumber, isString, isNull } from "../is/istype";

/**
 * 双端链表节点类
 */
class ListNode<T> {
  public value: T;
  public next: ListNode<T> | null;
  public prev: ListNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

/**
 * 双端链表类
 */
class LinkedList<T> {
  private _head: ListNode<T> | null;
  private _tail: ListNode<T> | null;
  private _count: number;

  constructor(...params:T[]) {
    this._head = null;
    this._tail = null;
    this._count = 0;
    if(params.length!==0){
      for (let index = 0; index < params.length; index++) {
        this.push( params[index]);
      }
    }
  }
  /**获取头节点*/
  get head(){
    return this._head;
  }

  /**获取尾节点*/
  get tail(){
    return this._tail;
  }


  /**链表的长度*/
  public get length(): number {
    return this._count;
  }

  /**
   * 在链表尾部添加节点
   * @param value 节点的值
   */
  public push(value: T): void {
    const node = new ListNode(value);

    if (!this._head) {
      this._head = node;
      this._tail = node;
    } else {
      this._tail!.next = node;
      node.prev = this._tail;
      this._tail = node;
    }

    this._count++;
  }

  /**
   * append 的别名方法
   * @param value 节点的值
   */
  public append(value: T): void {
    this.push(value);
  }

  /**
   * 在链表头部添加节点
   * @param value 节点的值
   */
  public pushLeft(value: T): void {
    const node = new ListNode(value);

    if (!this._head) {
      this._head = node;
      this._tail = node;
    } else {
      node.next = this._head;
      this._head.prev = node;
      this._head = node;
    }

    this._count++;
  }

  /**
   * addpenLeft的别名方法
   * @param value 节点的值
   */
  public appendLeft(value: T): void {
    this.pushLeft(value);
  }

  /**
   * 删除链表尾部节点
   * @returns 被删除的节点的值
   */
  public pop(): T | null {
    if (!this._tail) {
      return null;
    }

    const value = this._tail.value;

    if (this._count === 1) {
      this._head = null;
      this._tail = null;
    } else {
      this._tail = this._tail.prev;
      this._tail!.next = null;
    }

    this._count--;

    return value;
  }

  /**
   * 在链表头部添加节点
   * @param value 节点的值
   */
  public unshift(value: T): void {
    const node = new ListNode(value);

    if (!this._head) { // 如果链表为空
      this._head = node; // 新节点既是头节点也是尾节点
      this._tail = node;
    } else {
      node.next = this._head; // 新节点的next指向原头节点
      this._head.prev = node; // 原头节点的prev指向新节点
      this._head = node; // 新节点成为新的头节点
    }

    this._count++; // 链表长度加1
  }

  /**
   * 清空链表
   */
  public clear(): void {
    this._head = null;
    this._tail = null;
    this._count = 0;
  }

  /**
   * 删除指定节点
   * @param node 要删除的节点
   * @returns 被删除的节点的值
   */
  public remove(node: ListNode<T>): T | null {
    if (node.prev) {
      node.prev.next = node.next;
    } else {
      this._head = node.next;
    }

    if (node.next) {
      node.next.prev = node.prev;
    } else {
      this._tail = node.prev;
    }

    this._count--;

    return node.value;
  }

  /**
   * 删除指定位置的节点
   * @param index 要删除的节点的位置
   * @returns 被删除的节点的值
   */
  public drop(index: number): T | null {
    if (index < 0 || index >= this._count) {
      return null;
    }

    let current = this._head;

    for (let i = 0; i < index; i++) {
      current = current!.next;
    }

    return this.remove(current!);
  }

  /**
   * 对该链表进行切片，返回新的 LinkedList
   * @param start 切片的起始元素索引（包含）
   * @param end 切片的结束元素索引（不包含）
   */
  public slice(start:number, end:number){
    if(start < 0){
      start = this._count + start;
    }
    if(end < 0){
      end = this._count + end;
    }
    if(start < 0){
      start = 0;
    }
    if(end > this._count){
      end = this._count;
    }
    if(start >= end){
      return new LinkedList<T>();
    }
    let current = this._head;
    for(let i = 0; i < start; i++){
      current = current!.next;
    }
    const result = new LinkedList<T>();
    for(let i = start; i < end; i++){
      result.push(current!.value);
      current = current!.next;
    }
    return result;
  }

  /**
   * 如果LinkedList元素都为 number 时，用于与另外一个 LinkedList 元素对应相加，得到新的LinkedList返回。
   * 如果 LinkedList 元素都为 string 时，则返回对应字符串元素拼接组成的新LinkedList
   * @param list 要相加或拼接对应元素的 LinkedList
   * @returns 相加或拼接对应元素后的新 LinkedList
   */
  public add(list: LinkedList<T>): LinkedList<T> {
    const result = new LinkedList<T>();
    let current1 = this._head;
    let current2 = list._head;

    while (current1 && current2) {
      if (isNumber(current1.value) && isNumber(current2.value)) {
        result.push(current1.value + current2.value as T);
      } 
      else if (isString(current1.value) && isString(current2.value)) {
        result.push(current1.value + current2.value as T);
      } 
      else {
        throw TypeError('LinkedList 元素类型不匹配');
      }

      current1 = current1.next;
      current2 = current2.next;
    }

    return result;
  }

  /**
   * 获取指定位置的节点的值
   * @param index 节点的位置
   * @returns 节点的值
   */
  public get(index: number): T | null {
    if (index < 0 || index >= this._count) {
      return null;
    }

    let current = this._head;

    for (let i = 0; i < index; i++) {
      current = current!.next;
    }

    return current!.value;
  }

  /**
   * 判断链表中是否包含指定的值
   * @param value 要查找的值
   * @returns 是否包含指定的值
   */
  public includes(value: T): boolean {
    let current = this._head;

    while (current) {
      if (current.value === value) {
        return true;
      }

      current = current.next;
    }

    return false;
  }

  /**
   * includes 的别名方法
   * @param value 要查找的值
   * @returns 是否包含指定的值
   */
  public contains(value: T): boolean {
    return this.includes(value);
  }

  /**
   * 过滤链表中的节点
   * @param callback 过滤函数
   * @returns 过滤后的链表
   */
  public filter(callback: (value: T) => boolean): LinkedList<T> {
    const result = new LinkedList<T>();
    let current = this._head;

    while (current) {
      if (callback(current.value)) {
        result.push(current.value);
      }

      current = current.next;
    }

    return result;
  }

  /**
   * 映射链表中的节点
   * @param callback 映射函数
   * @returns 映射后的链表
   */
  public map<U>(callback: (value: T) => U): LinkedList<U> {
    const result = new LinkedList<U>();
    let current = this._head;

    while (current) {
      result.push(callback(current.value));
      current = current.next;
    }

    return result;
  }

  /**
     * 对链表进行快速排序的辅助函数
     * @param head 链表的头部节点
     * @param tail 链表的尾部节点
     * @returns 排序后的链表的头部节点
     */
  private _quickSort(head: ListNode<T> | null, tail: ListNode<T> | null): ListNode<T> | null {
    if (head === null || head === tail) {
      return head;
    }
  
    let pivot = head.value;
    let slow = head;
    let fast = head.next;
    // TODO: null values
    while (fast !== tail && !isNull(fast)) {
      if (fast.value < pivot) {
        slow = slow.next!;
        [slow.value, fast.value] = [fast.value, slow.value];
      }
      fast = fast.next!;
    }
  
    [head.value, slow.value] = [slow.value, head.value];
  
    const left = this._quickSort(head, slow);
    const right = this._quickSort(slow.next, tail);
  
    slow.next = right;
    if (left) {
      left.next = slow;
      return left;
    } else {
      return slow;
    }
  }

  /**
   * 对链表进行快速排序
   */
  public sort(): void {
    this._head = this._quickSort(this._head, this._tail);
  }

  /**
   * 对链表元素进行反转
   */
  public reverse(): void {
    let prev = null;
    let current = this._head;
    let next = null;

    while (current) {
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    this._head = prev;
  }

}

/**
 * 可迭代的列表类
 */
class List<T> {
  private _list: LinkedList<T>;

  constructor(...params:T[]) {
    this._list = new LinkedList<T>(...params);
  }

  get value(){
    return this._list
  }
  
  set value(list: LinkedList<T>){
    this._list = list;
  }

  /**
   * 在列表尾部添加元素
   * @param value 元素的值
   */
  public push(value: T): void {
    this._list.push(value);
  }


  /**
   * append的别名方法
   * @param value 元素的值
   */
  public append(value: T): void {
    this._list.append(value);
  }
  /**
   * 在列表头部添加元素
   * @param value 元素的值
   */
  public unshift(value: T): void {
    this._list.unshift(value);
  }

  /**
   * addpenLeft的别名方法
   * @param value 元素的值
   */
  public appendLeft(value: T): void {
    this._list.appendLeft(value);
  }

  /**
   * 删除列表尾部元素
   * @returns 被删除的元素的值
   */
  public pop(): T | null {
    return this._list.pop();
  }

  /**
   * 清空列表
   */
  public clear(): void {
    this._list.clear();
  }

  /**
   * 删除指定位置的元素
   * @param index 要删除的元素的位置
   * @returns 被删除的元素的值
   */
  public remove(index: number): T | null {
    return this._list.drop(index);
  }

  /**
   * 
   * @param value 元素的值
   */
  public add(value: LinkedList<T>): void {
    this._list.add(value);
  }

  /**
   * 获取指定位置的元素的值
   * @param index 元素的位置
   * @returns 元素的值
   */
  public get(index: number): T | null {
    return this._list.get(index);
  }

  /**
   * 判断列表中是否包含指定的值
   * @param value 要查找的值
   * @returns 是否包含指定的值
   */
  public includes(value: T): boolean {
    return this._list.includes(value);
  }

  /**
   * contains的别名方法
   * @param value 要查找的值
   * @returns 是否包含指定的值
   */
  public contains(value: T): boolean {
    return this._list.contains(value);
  }

  /**
   * 过滤列表中的元素
   * @param callback 过滤函数
   * @returns 过滤后的列表
   */
  public filter(callback: (value: T) => boolean): List<T> {
    const result = new List<T>();
    result._list = this._list.filter(callback);
    return result;
  }

  /**
   * 映射列表中的元素
   * @param callback 映射函数
   * @returns 映射后的列表
   */
  public map<U>(callback: (value: T) => U): List<U> {
    const result = new List<U>();
    result._list = this._list.map(callback);
    return result;
  }

  /**
   * 获取指定范围内的元素组成的新列表
   * @param start 起始位置（包含）
   * @param end 结束位置（不包含）
   * @returns 新列表
   */
  public slice(start: number, end: number): List<T> {
    const result = new List<T>();
    result.value = this._list.slice(start, end);
    return result;
  }

  /**
   * 纯基于整数位置的索引，用于按位置选择。
   * @param index 元素的位置
   * @returns 元素的值
   */
  public iloc(index: number): T | null {
    return this._list.get(index);
  }

  /**
   * 所有元素为number时，用于求和，所有元素为string时用于字符串拼接
   * @returns 求和或字符串拼接的结果
   */
  public sum(): number | string {
    let result: number | string = 0;
    let current = this._list.head;

    while (current) {
      if (isNumber(current.value)) {
        (result as number) += current.value;
      } 
      else if (isString(current.value)) {
        result = result + current.value;
      }
      current = current.next;
    }

    return result;
  }

  /**
   * 所有元素为number时返回最小值
   * @returns 最小值
   */
  public min(): number | null {
    let result: number | null = null;
    let current = this._list.head;

    while (current) {
      if (isNumber(current.value)) {
        if (result === null || current.value < result) {
          result = current.value;
        }
      }
      current = current.next;
    }

    return result;
  }

  /**
   * 所有元素为number时返回最大值
   * @returns 最大值
   */
  public max(): number | null {
    let result: number | null = null;
    let current = this._list.head;

    while (current) {
      if (isNumber(current.value)) {
        if (result === null || current.value > result) {
          result = current.value;
        }
      }
      current = current.next;
    }

    return result;
  }

  /**
   * 所有元素为number时返回平均值
   * @returns 平均值
   */
  public mean(): number | null {
    let sum = 0;
    let count = 0;
    let current = this._list.head;

    while (current) {
      if (isNumber(current.value)) {
        sum += current.value;
        count++;
      }
      current = current.next;
    }

    if (count === 0) {
      return null;
    }

    return sum / count;
  }

  /**
   * 所有元素为number时返回样本标准差
   * @returns 样本标准差
   */
  public std(): number | null {
    const mean = this.mean();
    if (mean === null) {
      return null;
    }

    let sum = 0;
    let count = 0;
    let current = this._list.head;

    while (current) {
      if (isNumber(current.value)) {
        sum += (current.value - mean) ** 2;
        count++;
      }
      current = current.next;
    }

    if (count <= 1) {
      return null;
    }

    return Math.sqrt(sum / (count - 1));
  }

  /**
   * 所有元素为number时返回无偏方差
   * @returns 无偏方差
   */
  public var(): number | null {
    const std = this.std();
    if (std === null) {
      return null;
    }

    return std ** 2;
  }

  /**
   * 所有元素为number时返回所有该LinkedList元素绝对值构成的新LinkedList
   * @returns 所有元素绝对值构成的新LinkedList
   */
  public abs(): List<number> {
    const result = new List<number>();
    let current = this._list.head;

    while (current) {
      if (isNumber(current.value)) {
        result.push(Math.abs(current.value));
      }
      current = current.next;
    }

    return result;
  }

  /**
   * 就地排序
   */
  public sort(){
    this._list.sort()
  }

  /**
   * 列表的长度
   */
  public get length(): number {
    return this._list.length;
  }

  /**
   * 列表的长度
   * - length 的同名 Getter.
   */
  public get size(): number {
    return this._list.length;
  }

  /**
   * 迭代器
   */
  public [Symbol.iterator](): Iterator<T> {
    let current = this._list.head;

    return {
      next: (): IteratorResult<T> => {
        if (!current) {
          return { done: true, value: null };
        }

        const value = current.value;
        current = current.next;

        return { done: false, value };
      },
    };
  }
}



export type {
  ListNode,
  LinkedList
}

export {
  List
}